#pragma once
#include <iostream>
#include <vector>
#include<string>
#include <assert.h>

using namespace std;

namespace Su
{
	//仿函数，将不同的数转换为整数
	template<class K>
	class HashFunc
	{
	public:
		size_t operator()(const K& key)
		{
			return key;
		}
	};

	template<>
	class HashFunc<string>
	{
	public:
		size_t operator()(const string& key)
		{
			size_t ret = 0;

			for (auto ch : key)
			{
				ret *= 131;
				ret += ch;
			}
			return ret;
		}
	};

	template<class T>
	class HashNode
	{
	public:
		typedef HashNode<T> Node;
		HashNode(const T& data)
		:_data(data)
		,_next(nullptr)
		{}

	
		T _data; //HashNode每个Node的结构都是由data和next组成
		Node* _next; //每一个方格都指向自己桶的下一个元素
	};
	
	//提前声明，由于迭代器会用HashTable，但是此时HashTabel还未声明
	template<class K, class T, class GetofKey>
	class HashTable;

	//关于迭代器的结尾：
	//当_cur为空则表示到了结尾
	//因此只要没到结尾或者哈希表为空，_cur永远不为空
	template<class K, class T, class Ptr, class Ref, class GetofKey, class HASHTBALE>
	class HashTableor
	{
	public:
		typedef HashTableor<K, T, T*, T&, GetofKey, HASHTBALE> iterator;
		typedef HashTableor<K, T, Ptr, Ref, GetofKey, HASHTBALE> Self;
		  typedef HashNode<T> Node;
		  typedef HashTable<K, T, GetofKey> HT;
		  Node* _cur;//用于指向桶的每个节点
		  HT* _pht;//用于遍历哈希表
		  
		HashTableor(Node* node, HT* pht)
			:_cur(node)
			,_pht(pht)
		{}

		HashTableor(const iterator& it)
			:_cur(it._cur)
			,_pht(it._pht)
		{}

		Ref operator*()
		{
			assert(_cur);
			return _cur->_data;
		}

		Ptr operator->()
		{
			assert(_cur);
			return &(operator*());
		}

		//pht是哈希表（结构）的指针，哈希表（结构）中的对象有：
		//vector<Node*> _table 和 size_t n
		//需要通过pht来访问_table
		Self operator++()
		{
			Node* old = _cur;
			if (_cur && _cur->_next == nullptr)
			{
				GetofKey kot;
				HashFunc<K> hf;
				size_t Hashi = hf(kot(_cur->_data)) % (_pht->_table).size();
				while (Hashi < (_pht->_table).size())
				{
					Hashi++;
					//如果下标超过了哈希表的大小，说明没有找到，返回原本的指向
					if (Hashi > _pht->_table.size()) { return Self(old, _pht); }
					if (_pht->_table[Hashi] != nullptr) { break; }
				}
				_cur = _pht->_table[Hashi];
			}
			else if (_cur && _cur->_next) { _cur = _cur->_next; }
			return Self(_cur, _pht);
		}
	};
	

	template<class K, class T, class GetofKey>
	class HashTable
	{
	public:
		//友元函数，迭代器是哈希表的友元，目的让迭代器可以使用哈希表的表
		friend HashTableor<K, T, T*, T&, GetofKey, HashTable>;
		friend HashTableor<K, T, const T*, const T&, GetofKey, HashTable>;
		
		typedef HashNode<T> Node;
		typedef HashTable<K, T, GetofKey> Self;
		typedef HashTableor<K, T, T*, T&, GetofKey, HashTable> iterator;
		typedef HashTableor<K, T, const T*, const T&, GetofKey, HashTable> const_iterator;

		//默认构造
		HashTable()
		{
			_table.resize(10, nullptr);
		}

		const_iterator begin() const
		{
			if (n == 0) return iterator(nullptr, this);
			for (auto& Hashi : _table)
			{
				if (Hashi != nullptr) return const_iterator(Hashi, this);
			}
		}

		const_iterator end() const
		{
			return const_iterator(nullptr, this);
		}
		

		iterator begin()
		{
			if (n == 0) return iterator(nullptr, this);
			for (auto& Hashi : _table)
			{
				if (Hashi != nullptr) return iterator(Hashi, this);
			}
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		//实现插入
		pair<iterator,bool> insert(const T& data)
		{
			//当平衡因子为1时进行扩容 
			//注意不能用capacity，因为下面需要用[ ]遍历旧表，而[ ]只能使用size以内的值
			//对size以外capacity以内的值使用[ ] 会报错
			GetofKey kot;
			if (n / _table.size() >= 1)
			{
				//不能直接扩容原table，会导致映射关系出错
				//创建一个新表，遍历旧表，将每个值头插到新表里
				//注意：这里不能用insert，insert会new一个新Node，这个行为的消耗太大
				vector<Node*> newtable(_table.size() * 3, nullptr);
				for (auto& Hashi : _table)
				{
					if (Hashi)
					{
						Node* cur = Hashi;
						Node* prev = nullptr;
						while (cur)
						{
							HashFunc<K> hf;
							size_t newHashi = hf(kot(cur->_data)) % newtable.size(); //找好映射关系
							prev = cur->_next;
							cur->_next = newtable[newHashi];
							newtable[newHashi] = cur;
							cur = prev;
						}
					}
				}
				_table.swap(newtable);
			}

			//1.先让数磨去table的大小，获得对应映射
			//①为了防止key的类型是string，需要使用仿函数将first转换成整数
			//HashFunc<K> hf;
			////size_t hashi = hf(GetofKey()(data)); 使用匿名对象的方法
			//size_t Hashi = hf(kot(data)) % _table.size(); //找好映射关系
			////准备插入，三种情况：
			////1.对应位置为空，直接插入
			////2.对应位置不为空，进行头插
			////3.对应位置不为空且key相等，返回false
			//Node* cur = _table[Hashi];
			//while (cur)
			//{
			//	//如果已经有该值，放弃插入
			//	if (kot(cur->_data) == kot(data))
			//	{
			//		return pair<iterator, bool>(iterator(cur, this), false);
			//	}
			//	cur = cur->_next;
			//}
			////走到这一步说明cur为空，即没有重复值，可以进行插入
			////①采用头插
			//Node* newnode = new Node(data);
			//newnode->_next = _table[Hashi];
			//_table[Hashi] = newnode;
			//n++;
			//return pair<iterator, bool>(iterator(cur,this), true);

			HashFunc<K> hf;
			size_t Hashi = hf(kot(data)) % _table.size(); //找好映射关系
			Node* cur = _table[Hashi];
			while (cur)
			{
				//如果已经有该值，放弃插入
				if (kot(cur->_data) == kot(data))
				{
					return pair<iterator, bool>(iterator(cur, this), false);
				}
				cur = cur->_next;
			}
			//走到这一步说明cur为空，即没有重复值，可以进行插入
			Node* newnode = new Node(data);
			newnode->_next = _table[Hashi];
			_table[Hashi] = newnode;
			n++;
			return pair<iterator, bool>(iterator(_table[Hashi],this), true);
		}

		bool print()
		{
			int num = 0;
			for (const auto& i : _table)
			{
				printf("[%d] ->", num++);
				Node* cur = i;
				GetofKey kot;
				while (cur)
				{
					cout << kot(cur->_data) << "->";
					cur = cur->_next;
				}
				cout << "NULL" << endl;
			}
			cout << endl;
			return true;
		}

		pair<iterator, bool> find(const K& key)
		{
			HashFunc<K> fc;
			GetofKey kot;
			size_t Hashi = fc(key) % _table.size();
			if (_table[Hashi])
			{
				Node* cur = _table[Hashi];
				while (cur)
				{
					if (kot(cur->_data) == key)
					{
						return pair<iterator, bool>(iterator(cur, this), true);
					}
					cur = cur->_next;
				}
			}
			//1.该位置的桶为空 2.cur没有找到要查找的值
			return pair<iterator,bool>(iterator(nullptr, this),false);//用空表示查找失败
		}

		bool erase(const K& key)
		{
			//pair<K,V>* ret = find(kv);
			if (find(key) == nullptr) return false;
			HashFunc<K> fc;
			size_t Hashi = fc(key) % _table.size();
			Node* cur = _table[Hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[Hashi] = cur->_next;
						n--;
						delete cur;
						return true;
					}
					prev->_next = cur->_next;
					n--;
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			
			return false;
		}
	private:
		vector<Node*> _table; //_table是一个指针数组，每个单元存储的是HashNode的地址
		size_t n = 0; //记录有效数据，当平衡因子为1（平均每个桶都有一个值）时扩容
	};
}